class Solution:
  def isMatch(self, s: str, p: str) -> bool:
    dp = [[False for j in range(len(p)+1)] for i in range(len(s)+1)]
    for ptr_s in range(len(s)+1):
      for ptr_p in range(len(p)+1):
        # 判断空正则串
        if ptr_p == 0:
          dp[ptr_s][ptr_p] = bool(ptr_s == 0)
        else:
          if p[ptr_p-1] != '*':
            if ptr_s >= 1 and (p[ptr_p-1] == s[ptr_s-1] or p[ptr_p-1] == '.'):
              dp[ptr_s][ptr_p] = dp[ptr_s-1][ptr_p-1]
          else:
            if ptr_p >= 2 and ptr_s >= 1 and (p[ptr_p-2] == s[ptr_s-1] or p[ptr_p-2] == '.'):
              dp[ptr_s][ptr_p] = dp[ptr_s][ptr_p] or dp[ptr_s-1][ptr_p]
            if ptr_p >= 2:
              dp[ptr_s][ptr_p] = dp[ptr_s][ptr_p] or dp[ptr_s][ptr_p-2]
    return dp[len(s)][len(p)]


'''
STATUS: LEARNT
TRIES:  N/A
TIME:   76 MS
MEMORY: 13.7 MB
'''
if __name__ == "__main__":
  solution = Solution()
  print(solution.isMatch(s='aa', p='a*c'))
